public class test4 {
    // https://leetcode.cn/problems/merge-k-sorted-lists/
//    public ListNode mergeKLists(ListNode[] lists) {
//        // 1. 创建一个小根堆
//        PriorityQueue<ListNode> heap=new PriorityQueue<>((v1,v2)->v1.val-v2.val);
//        // 2. 把所有的头结点放入小根堆
//        for(ListNode head:lists) {
//            if(head!=null) {    // 在入堆之前,先判断是否为空
//                heap.offer(head);
//            }
//        }
//        // 3. 合并链表
//        ListNode ret=new ListNode(0);// 虚拟头结点
//        ListNode prev=ret;
//        while(!heap.isEmpty()) {
//            ListNode t=heap.poll();
//            prev.next=t;
//            prev=t;
//            if(t.next!=null) {  // 在出掉堆顶元素后,将该节点的下一个节点入堆
//                heap.offer(t.next);
//            }
//        }
//        return ret.next;
//    }


    /*
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int left,int right) {
        if(left>right) return null;
        if(left==right) return lists[left];

        // 1. 平分数组
        int mid=(left+right)/2;
        // 2. 递归处理左右两部分
        ListNode l1=merge(lists,left,mid);
        ListNode l2=merge(lists,mid+1,right);
        // 3. 合并两个有序链表
        return mergeTwoList(l1,l2);
    }
    public ListNode mergeTwoList(ListNode l1,ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        // 两链表都不空时
        ListNode  head=new ListNode(0);
        ListNode cur1=l1,cur2=l2,prev=head;
        while(cur1!=null && cur2!=null) {
            if(cur1.val<=cur2.val) {
                prev.next=cur1;
                prev=cur1;
                cur1=cur1.next;
            } else {
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
        if(cur1!=null) prev.next=cur1;
        if(cur2!=null) prev.next=cur2;
        return head.next;
    }
     */
}
